package com.clstu.sort;

import java.util.Arrays;

/**
 * 研究基数排序(桶排序) --根据数的每一位(个.十.百.千.万...依次)进行排序
 * ,空间耗费大,但是速度特别快,典型的空间换时间
 */
public class RadixSort {
    public static void main(String[] args) {
         //测试是否正确
        int[] arr = new int[8000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random()*80000);
        }
        long start = System.currentTimeMillis();
        radixSort(arr);
        long end = System.currentTimeMillis();
        System.out.println("归并排序(桶排序)"+arr.length+"个数据耗时:"+(end-start)+"ms");//26ms
        System.out.println("排序后是否有序:"+isSorted(arr));
    }

    //编写方法实现基数排序(桶排序)
    public static void radixSort(int[] arr){
        //思路分析:
        //通排序过程:
        //准备10个桶,分别代表0,1,2,3,..10 第一轮,根据个位数放入对应的桶中,再依次取出放回原数组,实现个位的排序,
        //                             第二轮,根据十位数放入对应的桶中,再依次取出放回原数组,实现十位的排序,
        //                             第i轮,根据i位数放入对应的桶中,再依次取出放回原数组,实现i位的排序,直到最后没有位数为止,就排好序了
        //准备10个桶
        int[][] buckets= new int[10][arr.length];
        int[] bucketsElementCount = new int[10];//记录每个桶中放了多少的有效数据
        //遍历得到最大数的位数
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(max<arr[i]) max=arr[i];
        }
        int maxLen = (max+"").length();
        //循环排序
        for (int i = 0,x=1; i < maxLen; i++,x*=10) {
            for (int j = 0; j < arr.length; j++) {
                //得到比较的位数,放到对应的桶中,并将 对应的桶的有效数据个数++
                int n = (arr[j]/x)%10;//得到桶的编号
                buckets[n][bucketsElementCount[n]++] = arr[j];
            }
            //依次放回原数组,实现第i位的排序,并将bucketsElementCount清0,下一次循环可以接着使用
            int index = 0;
            for (int j = 0; j < 10; j++) {
                //如果桶中没有数据,就不用放回原数组
                if(bucketsElementCount[j]!=0){
                    //放回原数组
                    for (int k = 0; k < bucketsElementCount[j]; k++) {
                        arr[index++]=buckets[j][k];
                    }
                    //清0
                    bucketsElementCount[j] = 0;
                }
            }
        }
        //完活
    }

    //编写方法判断是否数组有序
    public static boolean isSorted(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            if(arr[i]>arr[i+1]) return false;
        }
        return true;
    }
}
